package com.swjd.search;

import java.util.ArrayList;

/**
 * 二分查找
 */
public class BinarySearch {
    public static void main(String[] args) {
        //二分查找数组必须有序
        int arr[] = {1, 8, 10, 89, 1000, 1000, 1000, 1234};
     /*   int test = test(arr, 0, arr.length - 1, 1000);
        System.out.println(test);*/

        ArrayList arrayList = test2(arr, 0, arr.length - 1, 45);
        System.out.println(arrayList);

    }

    /**
     * 二分查找法
     *
     * @param arr   传入的数组
     * @param left  左起始下标
     * @param right 右结束下标
     * @param value 查找的值
     * @return 查找的值对应的下标 未查找到返回-1
     */
    public static int test(int[] arr, int left, int right, int value) {
        //确定中间值
        int center = (left + right) / 2;
        //当left>right时，说明已经递归完毕
        if (left > right) {
            return -1;
        }
        if (value > arr[center]) {//向右递归
            return test(arr, center + 1, right, value);
        } else if (value == arr[center]) {
            return center;
        } else { //向左递归 (value < arr[center])
            return test(arr, left, center - 1, value);
        }
    }

    /**
     * 重复数据一起查找
     *
     * @param arr
     * @param left
     * @param right
     * @param value
     * @return 结果集
     */
    public static ArrayList test2(int[] arr, int left, int right, int value) {
        //确定中间值
        int center = (left + right) / 2;
        //当left>right时，说明已经递归完毕
        if (left > right) {
            return null;
        }
        if (value > arr[center]) {//向右递归
            return test2(arr, center + 1, right, value);
        } else if (value == arr[center]) {
            ArrayList<Integer> list = new ArrayList<>();
            int temp = center - 1;
            while (true) {
                if (temp < 0 || arr[temp] != value) {
                    //如果向左找没有找到
                    break;
                }
                //找到了就放入集合
                list.add(temp);
                temp--;//继续左移
            }
            list.add(center);
            temp = center + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != value) {
                    //如果向右找没有找到
                    break;
                }
                //找到了就放入集合
                list.add(temp);
                temp++;//继续右移
            }
            return list;//都操作完后返回结果集

        } else { //向左递归 (value < arr[center])
            return test2(arr, left, center - 1, value);
        }
    }
}
